package java学习.leetcode.editor.cn;

import com.sun.source.tree.CompilationUnitTree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 刘世锦
 * 2022-12-24 19:22:50	 当前时间
 */
//给你两棵二叉树： root1 和 root2 。 
//
// 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠
//，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。 
//
// 返回合并后的二叉树。 
//
// 注意: 合并过程必须从两个树的根节点开始。 
//
// 
//
// 示例 1： 
//
// 
//输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
//输出：[3,4,5,5,4,null,7]
// 
//
// 示例 2： 
//
// 
//输入：root1 = [1], root2 = [1,2]
//输出：[2,2]
// 
//
// 
//
// 提示： 
//
// 
// 两棵树中的节点数目在范围 [0, 2000] 内 
// -104 <= Node.val <= 104 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 
// 👍 1129 👎 0

public class 合并二叉树{
	public static void main(String[] args) {
		Solution solution = new 合并二叉树().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

	/** 复习  @author 刘世锦
	 *  @date  2023/2/7 10:36
	 */

	public TreeNode mergeTreesByReview(TreeNode root1, TreeNode root2) {

		if (root1==null&&root2!=null){
			return root2;
		}else if (root1!=null&&root2==null) {
			return root1;
		}else if (root1!=null&&root2!=null) {
			TreeNode node = new TreeNode();
			node.val = root1.val+root2.val;
			node.left = mergeTrees(root1.left,root2.left);
			node.right = mergeTrees(root1.right,root2.right);
			return node;
		}
		return null;

	}


	public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
		Queue<TreeNode> queueMerge = new LinkedList<>();
		Queue<TreeNode> queue1 = new LinkedList<>();
		Queue<TreeNode> queue2 = new LinkedList<>();
		if (root1!=null&&root2!=null){
			queue1.offer(root1);
			queue2.offer(root2);
			TreeNode rootMerge = new TreeNode(root1.val + root2.val);
			queueMerge.offer(rootMerge);
			while (!queue1.isEmpty()){
				TreeNode node1 = queue1.poll();
				TreeNode node2 = queue2.poll();
				TreeNode nodeMerge = queueMerge.poll();
				if (node1.left!=null&&node2.left!=null){
					queue1.offer(node1.left);
					queue2.offer(node2.left);
					TreeNode left = new TreeNode(node1.left.val + node2.left.val);
					nodeMerge.left = left;
					queueMerge.offer(left);
				}else if (node1.left!=null){
					nodeMerge.left = node1.left;
				}else {
					nodeMerge.left = node2.left;
				}
				if (node1.right!=null&&node2.right!=null){
					queue1.offer(node1.right);
					queue2.offer(node2.right);
					TreeNode right = new TreeNode(node1.right.val + node2.right.val);
					nodeMerge.right = right;
					queueMerge.offer(right);
				}else if (node1.right!=null){
					nodeMerge.right = node1.right;
				}else {
					nodeMerge.right = node2.right;
				}

			}
			return rootMerge;
		}else if (root1!=null){
			return root1;
		}
		return root2;

	}




		// 复习end





	// 复习start
	TreeNode noderoot ;
	public TreeNode mergeTreesReview_DFS(TreeNode root1, TreeNode root2) {

		Queue<TreeNode> queue1 = new LinkedList<>();
		Queue<TreeNode> queue3 = new LinkedList<>();

		if (root1==null&&root2==null){
			return null;
		}else if (root1!=null&&root2==null){
			noderoot = root1;
			return noderoot;
		}else if (root2!=null&&root1==null){
			noderoot =  root2;
			return noderoot;
		}else {
			noderoot = new TreeNode(root1.val + root2.val);
			queue1.offer(root1);
			queue1.offer(root2);
			queue3.offer(noderoot);
			while (!queue1.isEmpty() ) {
				TreeNode node1 = queue1.poll();
				TreeNode node2 = queue1.poll();
				TreeNode treeNode = queue3.poll();
				if (node1.left != null && node2.left != null) {
					treeNode.left = new TreeNode(node1.left.val + node2.left.val);
					queue1.offer(node1.left);
					queue1.offer(node2.left);
					queue3.offer(treeNode.left);
				} else if (node1.left != null) {
					treeNode.left = node1.left;
				} else if (node2.left != null) {
					treeNode.left = node2.left;
				}

				if (node1.right != null && node2.right != null) {
					treeNode.right = new TreeNode(node1.right.val + node2.right.val);
					queue1.offer(node1.right);
					queue1.offer(node2.right);
					queue3.offer(treeNode.right);
				} else if (node1.right != null) {
					treeNode.right = node1.right;
				} else if (node2.right != null) {
					treeNode.right = node2.right;
				}
			}
		}
		return noderoot;
	}

	public TreeNode mergeTrees4(TreeNode root1, TreeNode root2) {

		Queue<TreeNode> queue1 = new LinkedList<>();
		Queue<TreeNode> queue2 = new LinkedList<>();
		Queue<TreeNode> queue3 = new LinkedList<>();

		if (root1==null&&root2==null){
			return null;
		}else if (root1!=null&&root2==null){
			noderoot = root1;
			return noderoot;
		}else if (root2!=null&&root1==null){
			noderoot =  root2;
			return noderoot;
		}else {
				noderoot = new TreeNode(root1.val + root2.val);
				queue1.offer(root1);
				queue2.offer(root2);
				queue3.offer(noderoot);
				while (!queue1.isEmpty() && !queue2.isEmpty()) {
					TreeNode node1 = queue1.poll();
					TreeNode node2 = queue2.poll();
					TreeNode treeNode = queue3.poll();
					if (node1.left != null && node2.left != null) {
						treeNode.left = new TreeNode(node1.left.val + node2.left.val);
						queue1.offer(node1.left);
						queue2.offer(node2.left);
						queue3.offer(treeNode.left);
					} else if (node1.left != null) {
						treeNode.left = node1.left;
					} else if (node2.left != null) {
						treeNode.left = node2.left;
					}

					if (node1.right != null && node2.right != null) {
						treeNode.right = new TreeNode(node1.right.val + node2.right.val);
						queue1.offer(node1.right);
						queue2.offer(node2.right);
						queue3.offer(treeNode.right);
					} else if (node1.right != null) {
						treeNode.right = node1.right;
					} else if (node2.right != null) {
						treeNode.right = node2.right;
					}
				}
		}
		return noderoot;
	}




	public TreeNode mergeTrees3(TreeNode root1, TreeNode root2) {
		if (root1==null&&root2==null){
			return null;
		}else if (root1!=null&&root2==null){
 			return root1;
		}else if (root2!=null&&root1==null){
 			return  root2;
		}
		TreeNode node = new TreeNode(root1.val+root2.val);
		TreeNode left = mergeTrees3(root1.left, root2.left);
		TreeNode right = mergeTrees3(root1.right, root2.right);
		node.left = left;
		node.right = right;
		return node;
	}


	// 复习end




    public TreeNode mergeTrees1(TreeNode root1, TreeNode root2) {
		if (root1==null&&root2==null){
			return null;
		} else if (root1==null){
			return root2;
		}else if (root2==null){
			return root1;
		}
		TreeNode node = new TreeNode();
		node.val = root1.val+root2.val;
		node.left = mergeTrees(root1.left,root2.left);
		node.right = mergeTrees(root1.right,root2.right);
		return node;
	}

	/**
	 * queue 广度遍历
	 *
	 * _  4 5    _
	 * _  2   1 4_
	 * _  6      _
	 * queue1、queue2 为 子树1、2
	 * queue3 为 合并的树3
	 *
	 */
	public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
		Queue<TreeNode> queue1 = new LinkedList<>();
		Queue<TreeNode> queue2 = new LinkedList<>();
		Queue<TreeNode> queue3 = new LinkedList<>();
		TreeNode current = new TreeNode();
		if (root1==null&&root2==null){
			return null;
		} else
		if (root1==null){
			return root2;
		}else if (root2==null){
			return root1;
		}
		if (root1!=null&&root2!=null){
			queue1.offer(root1);
			queue2.offer(root2);
			current.val = root1.val+root2.val;
			queue3.offer(current);
			while (!queue1.isEmpty()&&!queue2.isEmpty()) {

				TreeNode node1 = queue1.poll();
				TreeNode node2 = queue2.poll();
				TreeNode curNode = queue3.poll();
				/**
				 * 	都不为空 ，合并值
				 *  queue1、queue2 需要保证处理的是同一位置节点：（都是左节点，都是右节点）
				 *
 				 */
				if (node1.left != null && node2.left != null) {
					curNode.left = new TreeNode(node1.left.val + node2.left.val);
					queue1.offer(node1.left);
					queue2.offer(node2.left);
					queue3.offer(curNode.left);

				// root2为空，直接取root1, 算是取叶子节点，下面也没有其他节点了，故不需要放进queue中

				} else if (node2.left != null) {
					curNode.left = node2.left;
				// 取另一个
				} else if (node1.left != null) {
					curNode.left = node1.left;
				}

				if (node1.right != null && node2.right != null) {
					curNode.right = new TreeNode(node1.right.val + node2.right.val);
					queue1.offer(node1.right);
					queue2.offer(node2.right);
					queue3.offer(curNode.right);
				} else if (node2.right != null) {
					curNode.right = node2.right;
				} else if (node1.right != null) {
					curNode.right = node1.right;
				}

			}
		}

		return  current;
	}


	}
//leetcode submit region end(Prohibit modification and deletion)

}
